/*
 * This code is provided AS-IS.
 * You may use this code in any way you see fit, EXCEPT as the answer to a homework
 * problem or as part of a term project in which you were expected to arrive at this
 * code yourself.  
 * 
 * Copyright (C) 2005 Neil Jones.
 *
 */
package AlignmentHelper;

public class LCS {
// These are "constants" which indicate a direction in the backtracking array.
    private static final int NEITHER = 0;

    private static final int UP = 1;

    private static final int LEFT = 2;

    private static final int UP_AND_LEFT = 3;


    public static String LCSAlgorithm(String a, String b) {
        int n = a.length();
        int m = b.length();
        int S[][] = new int[n + 1][m + 1];
        int R[][] = new int[n + 1][m + 1];
        int ii, jj;

        // It is important to use <=, not <.  The next two for-loops are initialization
        for (ii = 0; ii <= n; ++ii) {
            S[ii][0] = 0;
            R[ii][0] = UP;
        }
        for (jj = 0; jj <= m; ++jj) {
            S[0][jj] = 0;
            R[0][jj] = LEFT;
        }

        // This is the main dynamic programming loop that computes the score and
        // backtracking arrays.
        for (ii = 1; ii <= n; ++ii) {
            for (jj = 1; jj <= m; ++jj) {

                if (a.charAt(ii - 1) == b.charAt(jj - 1)) {
                    S[ii][jj] = S[ii - 1][jj - 1] + 1;
                    R[ii][jj] = UP_AND_LEFT;
                } else {
                    S[ii][jj] = S[ii - 1][jj - 1] + 0;
                    R[ii][jj] = NEITHER;
                }

                if (S[ii - 1][jj] >= S[ii][jj]) {
                    S[ii][jj] = S[ii - 1][jj];
                    R[ii][jj] = UP;
                }

                if (S[ii][jj - 1] >= S[ii][jj]) {
                    S[ii][jj] = S[ii][jj - 1];
                    R[ii][jj] = LEFT;
                }
            }
        }

        // The length of the longest substring is S[n][m]
        ii = n;
        jj = m;
        int pos = S[ii][jj] - 1;
        char lcs[] = new char[pos + 1];

        // Trace the backtracking matrix.
        while (ii > 0 || jj > 0) {
            if (R[ii][jj] == UP_AND_LEFT) {
                ii--;
                jj--;
                lcs[pos--] = a.charAt(ii);
            } else if (R[ii][jj] == UP) {
                ii--;
            } else if (R[ii][jj] == LEFT) {
                jj--;
            }
        }

        return new String(lcs);
    }


    public static String lcsSimple(String x, String y) {
        int M = x.length();
        int N = y.length();

        // opt[i][j] = length of LCS of x[i..M] and y[j..N]
        int[][] opt = new int[M + 1][N + 1];

        // compute length of LCS and all subproblems via dynamic programming
        for (int i = M - 1; i >= 0; i--) {
            for (int j = N - 1; j >= 0; j--) {
                if (x.charAt(i) == y.charAt(j)) {
                    opt[i][j] = opt[i + 1][j + 1] + 1;
                } else {
                    opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);
                }
            }
        }

        // recover LCS itself and print it to standard output
        String res = "";
        int i = 0, j = 0;
        while (i < M && j < N) {
            if (x.charAt(i) == y.charAt(j)) {
                res = res + x.charAt(i);
                i++;
                j++;
            } else if (opt[i + 1][j] >= opt[i][j + 1]) {
                i++;
            } else {
                j++;
            }
        }

        return res;
    }
}
